1. Field of Invention
The present invention relates to a digital image processing method and apparatus. More particularly, the present invention relates to a digital image processing method and apparatus using discrete wavelet transform (DWT) algorithm.
2. Description of Related Art
The Discrete Wavelet Transform (DWT) provides excellent characteristics in time-frequency domain analysis and has been extensively used in many applications. Those applications include image compression, biomedical image processing, and signal analysis etc. Even the latest static image encoding/decoding standard, JPEG 2000, chose a kind of DWT, called lifting-based DWT as its core computation algorithm. The DWT module is one of the sophisticated and complex modules used in designing JPEG 2000 hardware architecture.
With reference to FIG. 1, different kinds of DWT circuits have been developed and published and the DWT has been extensively used in the image processing field. The lifting scheme is one of the most referenced and modified DWT. The disadvantage of the lifting scheme DWT is that the critical path is too long. The critical path has a computation delay time of four multipliers and eight adders.
The detailed algorithm of the forward 9/7 lifting scheme discrete wavelet transform is,
                              step          ⁢                                          ⁢          1          ⁢                      :                    ⁢                                          ⁢                      Y            ⁡                          (                                                2                  ⁢                  n                                +                1                            )                                      ←                                            X              ext                        ⁡                          (                                                2                  ⁢                  n                                +                1                            )                                +                      α            ×                          [                                                                    X                    ext                                    ⁡                                      (                                          2                      ⁢                      n                                        )                                                  +                                                      X                    ext                                    ⁡                                      (                                                                  2                        ⁢                        n                                            +                      2                                        )                                                              ]                                                          (        1        )                                          step          ⁢                                          ⁢          2          ⁢                      :                    ⁢                                          ⁢                      Z            ⁡                          (                                                2                  ⁢                  n                                +                2                            )                                      ←                                            X              ext                        ⁡                          (                                                2                  ⁢                  n                                +                2                            )                                +                      β            ×                          [                                                Y                  ⁡                                      (                                                                  2                        ⁢                        n                                            +                      1                                        )                                                  +                                  Y                  ⁡                                      (                                                                  2                        ⁢                        n                                            +                      3                                        )                                                              ]                                                          (        2        )                                          step          ⁢                                          ⁢          3          ⁢                      :                    ⁢                                          ⁢                      H            ⁡                          (                                                2                  ⁢                  n                                +                3                            )                                      ←                              Y            ⁡                          (                                                2                  ⁢                  n                                +                3                            )                                +                      γ            ×                          [                                                Z                  ⁡                                      (                                                                  2                        ⁢                        n                                            +                      2                                        )                                                  +                                  Z                  ⁡                                      (                                                                  2                        ⁢                        n                                            +                      4                                        )                                                              ]                                                          (        3        )                                          step          ⁢                                          ⁢          4          ⁢                      :                    ⁢                                          ⁢                      L            ⁡                          (                                                2                  ⁢                  n                                +                4                            )                                      ←                              Z            ⁡                          (                                                2                  ⁢                  n                                +                4                            )                                +                      δ            ×                          [                                                H                  ⁡                                      (                                                                  2                        ⁢                        n                                            +                      3                                        )                                                  +                                  H                  ⁡                                      (                                                                  2                        ⁢                        n                                            +                      5                                        )                                                              ]                                                          (        4        )                                          step          ⁢                                          ⁢          5          ⁢                      :                    ⁢                                          ⁢                      Hout            ⁡                          (                                                2                  ⁢                  n                                +                3                            )                                      ←                              (                          -              K                        )                    ×                      H            ⁡                          (                                                2                  ⁢                  n                                +                3                            )                                                          (        5        )                                          step          ⁢                                          ⁢          6          ⁢                      :                    ⁢                                          ⁢                      Lout            ⁡                          (                                                2                  ⁢                  n                                +                4                            )                                      ←                              1            K                    ×                      L            ⁡                          (                                                2                  ⁢                  n                                +                4                            )                                                          (        6        )            
and the coefficients,
         {                                        α            =                          -              1.586134342                                                                        β            =                          -              0.052980118                                                                        γ            =            0.882911075                                                            δ            =            0.443506852                                                            K            =            1.230174105                              
wherein, Xext represents source image data, Hout represents high pass output, Lout represents low pass output, and the coefficients Y, Z, H and L are temporary values during the computation and must be provided for the next computation step. Y(n) represents the Y number of n-th wavelets in the algorithm.
Refer to FIG. 2. FIG. 2 illustrates an analytic diagram of the forward 9/7 discrete wavelets transform. FIG. 2 clearly shows that the data are aggregated at even time terms T(2n) to process along the time axis, while there are no computations at odd time terms T(2n+1) along the time axis where the system waits for associated data for processing at those odd time terms.
Refer to FIG. 3. FIG. 3 illustrates an analytic diagram of another modified DWT, called pipeline lifting scheme. The pipeline lifting scheme shortens the critical path of the lifting scheme, but uses eight registers. Although, the pipeline lifting scheme overcomes the problem of the lifting scheme, the circuit area is increased because of the presence of the registers.
Refer to FIG. 4. FIG. 4 illustrates an analytic diagram of another kind of DWT, called flipping scheme. The flipping scheme is developed based on the lifting scheme. The flipping scheme removes multiplication of some computation steps from the algorithm so as to remove the multipliers from the critical path. Comparing the flipping scheme with the lifting scheme, the critical path of the lifting scheme is accumulated by the computation time of the four multipliers and eight adders, and the critical path of the flipping scheme is accumulated by the computation time of one multiplier and five adders. Therefore, the flipping scheme shortens the critical path of the lifting scheme by removing the multipliers.
Furthermore, a number of temporal coefficient buffers significantly dominate the size of the circuit area in designing two-dimensional (2D) DWT circuit. The image data scanning method adopted by the circuit significantly dominates the power consumption performance.
Refer to FIG. 5a and FIG. 5b. In FIG. 5a and FIG. 5b a 1-level 2-dimensional DWT system is used an example. 1-level means that the DWT circuit analyzes one level of the two-dimensional image at a time. In other words, the DWT circuit uses a two-dimensional (2-D) DWT module.
The 2-D DWT circuit comprises an external memory 700 and a 2-D DWT module 701. The size of the external memory 700 must be N/2×N/2 words. However, the 2-D DWT module 701 needs a temporal coefficient buffer 702 to store temporal reusable data and with a size of K×N words, wherein K represents a number of necessary temporal buffers adopted by the 2-D DWT module 701. The number of the temporal buffers depends on the DWT circuit adopted by the system.
Refer to FIG. 6. FIG. 6 illustrates the data processing process. For processing a 2-D image, each step performs a 1-D row DWT and a 1-D column DWT for the 2-D image and outputs the data after the completion of both 1-D DWTs. The HH (high pass outputs in both row and column) data, HL (low pass outputs in both row and column) data, and LH (low pass output in row and high pass in column) data can be directly outputted when outputting the computation result. The LL data should be determined whether it meets the demands of resolution or not. If the LL data has not reached the demands, then the LL data should be restored into the external memory 700 for the next transforming computation.
Therefore, the conventional 2-D DWT scheme must use the external memory 700 to transpose data. The use of the external memory 700 increases the hardware expense and the size of the circuit area.
Therefore, there is a need to provide an improved DWT architecture to mitigate or obviate the aforementioned problems.